/**
 * 这是 LeetCode 第 45. 跳跃游戏 II 的解决方案
 * https://leetcode.cn/problems/jump-game-ii
 */
class JumpGameII {
    /**
     * 方法：贪心算法
     * 
     * 功能：计算从数组第一个位置跳到最后一个位置所需的最小跳跃次数
     * 
     * 实现逻辑：
     * 1. 维护三个变量:
     *    - step: 记录跳跃次数
     *    - curRight: 当前能到达的最远位置(当前桥的右端点)
     *    - nextRight: 下一步能到达的最远位置(下一座桥的右端点的最大值)
     * 2. 遍历数组到倒数第二个位置:
     *    - 更新nextRight为当前位置能跳到的最远距离
     *    - 当到达curRight时，更新curRight为nextRight并增加step
     * 3. 返回最小跳跃次数step
     * 
     * 时间复杂度：O(n)，其中n为数组长度，只需要遍历一次数组
     * 
     * 空间复杂度：O(1)，只使用了常数个变量
     */
    public int jump(int[] nums) {
        int step = 0;
        int curRight = 0; //已建造桥的右端点
        int nextRight = 0; //下一座桥的右端点的最大值
        int len = nums.length;
        for(int i = 0; i < len - 1; i++){
            nextRight = Math.max(nextRight, i + nums[i]);
            if(i == curRight){
                curRight = nextRight;
                step++;
            }
        }
        return step;
    }
}